import java.util.Arrays;

public class insertSort {
    public static void main(String[] args) {
        int[]array={99,4,5,6,1,3,2,8,5,4,1,3,1,8,4,7,1,9};
        int[]bad={99,88,55,22,11,8,7,4,3,2,1};
        //直接插入排序
        //int[] arr=insertSort(bad);
        //希尔排序
        int []arr=shellSort(bad,5);
        System.out.println(Arrays.toString(arr));

    }

    /**排序大分类：《插入排序》
     * 直接插入排序
     * 时间复杂度：(n^2)
     * 稳定性：稳定的
     * 适用场合：数组元素趋于有序的数组。
     * @param array 待排序数组
     * @return 返回排序好的数组
     */
    public static  int[] insertSort(int[]array){
        //考虑数组元素个数为1个
        if(array.length==1) return array;
        for (int i = 1; i < array.length; i++) {
            int minIndex=array[i];
            int j;
            for ( j = i-1; j>=0; j--) {
                if(array[j]>minIndex){
                    array[j+1]=array[j];
                }else{
                    array[j+1]=minIndex;
                    break;
                }

            }
            array[j+1]=minIndex;
        }
        return array;
    }


    /**排序大分类：《插入排序》
     * 直接插入排序
     * 时间复杂度：(n^2)
     * 稳定性：不稳定的
     * 适用场合：插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
     * 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位，可以理解为直接插入排序的改良版。。
     * @param array 待排序数组
     * @return 返回排序好的数组
     */
    public static int[] shellSort(int[]array,int gap){
            int i=gap;
            int j=i-gap;
        for (i = gap; i >1 ; i/=2) {
            shell(array,gap);
            gap/=2;
        }
        shell(array,1);
        return array;
    }
    public static void shell(int[]array,int gap){
        for (int i = gap; i < array.length; i++) {
            int minIndex=array[i];
            int j=i-gap;
            for (j = i-gap; j >=0; j-=gap) {
                if(array[j]>minIndex){
                    array[j+gap]=array[j];
                }else{
                    array[j+gap]=minIndex;
                    break;
                }
            }
            array[j+gap]=minIndex;

        }
    }
}

